import functools


class Solution(object):
    def getLengthOfOptimalCompression(self, s, k):
        n = len(s)
        t = n - k

        def find_len(val):
            if val == 1:
                return 1
            else:
                return 1 + len(str(val))

        @functools.cache
        def dfs(i, m):
            if m == 0:
                return 0
            if n - i < m:
                return float('inf')
            if i == n:
                return 0
            min_val = float('inf')
            min_val = min(min_val, dfs(i + 1, m))
            same = 0
            for j in range(i, n):
                if s[j] == s[i]:
                    same += 1
                    min_val = min(min_val, find_len(same) + dfs(j + 1, m - same))
            return min_val

        return dfs(0, t)

data = Solution()
s = "aaabcccd"
k = 2
print(data.getLengthOfOptimalCompression(s, k))
